/**
 * 
 */
package datastructure;

import java.util.Collections;
import java.util.Stack;
/** Reference
 * http://www.necessaryandsufficient.net/2009/01/stack-with-constant-time-minimum/
 * Problem: You need to implement a stack data structure that can also report the minimum element in constant-time.
 *
 * Solution: This is not all that difficult if you think about it. Regular stacks support push() and pop() functions. We need to add a new read-only property, Minimum. You can't just add a new variable to track the minimum because when the stack is popped you wouldn't be know how to update the minimum variable without scanning through all items in the stack which would require you to pop and re-push each item, which is downright ugly. So we need to keep some auxiliary list of the stack items so we can update the minimum variable after we pop items. A clever way to do that is to use another stack that stores the minimum of all items in the stack. The minimum value is calculated when items are pushed to the stack and when items are popped from the stack we also pop from the minStack to reveal the new minimum value.
 */


/**
 * @author michaelyi
 *
 */
public class MinStackConstantTime<E extends Comparable<? super E>> {

	Stack<E> dataStack = null;
	Stack<E> minStack = null;
	
	public void push(E element) {
		if (null == element)	return;
		
		dataStack.push(element);
		if (minStack.isEmpty() || element.compareTo(minStack.peek()) <= 0) {
			minStack.push(element);
		}
	}
	
	public E pop() {
		if (dataStack.isEmpty()) return null;
		
		assert(minStack.peek().compareTo(dataStack.peek()) <= 0);
		if (dataStack.peek().compareTo( minStack.peek() ) == 0) {
			minStack.pop();
		}
		
		return dataStack.pop();
	}
	
	public E peek() {
		return dataStack.peek();
	}
	
	public int size() {
		return dataStack.size();
	}
	
	public E getMinimum() {
		return minStack.peek();
	}

	/**
	 * 
	 */
	public MinStackConstantTime() {
		dataStack = new Stack<E>();
		minStack = new Stack<E>();
	}
	
	@Override
	public String toString() {
		StringBuffer sb = new StringBuffer();
		sb.append("{");
		for (E e : dataStack) {
				sb.append(e).append(',');
		}
		sb.deleteCharAt(sb.length() - 1);
		sb.append("}");
		return sb.toString();
	}
	
	public static void main(String[] args) {
		System.out.println("Min Stack");
		MinStackConstantTime<Integer> stack = new MinStackConstantTime<Integer>();
		stack.push(5); 
		stack.push(2);
		stack.push(3);
		stack.push(2);
		stack.push(1);
		while (stack.size() > 0) {
			System.out.printf("%s, min : %d\n", stack.toString(), stack.getMinimum());
			stack.pop();
		}
	}
}
